Лемма о рукопожатиях
Лемма о рукопожатиях
Формулировка:
В ориентированом графе $G = (V, E)$: $$\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |E|$$ В неориентированом графе $G = (V, E)$: $$\sum_{v \in V} d(v) = 2|E|$$
Формулировка:
В ориентированом графе $G = (V, E)$: $$\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = |E|$$ В неориентированом графе $G = (V, E)$: $$\sum_{v \in V} d(v) = 2|E|$$